package club.vann.nowcoder;

import com.sun.tools.javadoc.Start;

/**
 * <p>难度：Medium</p>
 * <p>题目：二分查找</p>
 * <p>描述：请实现有重复数字的升序数组的二分查找
 * 给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
 * 示例1
 * 输入
 * 复制
 * [1,2,4,4,5],4
 * 返回值
 * 复制
 * 2
 * 说明
 * 从左到右，查找到第1个为4的，下标为2，返回2
 * 示例2
 * 输入
 * 复制
 * [1,2,4,4,5],3
 * 返回值
 * 复制
 * -1
 * 示例3
 * 输入
 * 复制
 * [1,1,1,1,1],1
 * 返回值
 * 复制
 * 0</p>
 * @author vann
 * @program now-coder
 * @description
 * @date 2021-03-19:16:53:05
 */
public class NC105 {
    public static void main(String[] args) {
        NC105 nc105 = new NC105();

//        System.out.println("Result["+TestCase.ANS+"] : " + nc105.search(TestCase.NUMS, TestCase.TARGET));
//        System.out.println("Result["+TestCase.ANS1+"] : " + nc105.search(TestCase.NUMS1, TestCase.TARGET1));
//        System.out.println("Result["+TestCase.ANS2+"] : " + nc105.search(TestCase.NUMS2, TestCase.TARGET2));
        System.out.println("Result["+TestCase.ANS3+"] : " + nc105.search(TestCase.NUMS3, TestCase.TARGET3));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 如果目标值存在返回下标，否则返回 -1
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if(nums == null || nums.length == 0) {
            return -1;
        }

        int len = nums.length;
        int left = 0, right = len-1;
        while(left <= right) {
            if(target < nums[left] || nums[right] < target) {
                return -1;
            } else if(target == nums[left]) {
                return left;
            } else if(target == nums[right]) {
                left ++;
            } else {
                left ++;
                right --;
            }
        }
        return -1;
    }

    static class TestCase {
        public static int ANS = 2;
        public static int[] NUMS = {1,2,4,4,5};
        public static int TARGET = 4;

        public static int ANS1 = -1;
        public static int[] NUMS1 = {1,2,4,4,5};
        public static int TARGET1 = 3;

        public static int ANS2 = 0;
        public static int[] NUMS2 = {1,1,1,1,1};
        public static int TARGET2 = 1;

        public static int ANS3 = 3;
        public static int[] NUMS3 = {1,2,3,8,9};
        public static int TARGET3 = 8;
    }
}
